package topo;
import java.util.*;
public class Ex207 {
    static class Solution1 {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            //入度表，记录当前节点的入度值
            int[] inDgree = new int[numCourses]; //默认数组的初始值为全0

            //邻接表，记录当前节点的所有出度节点
            Map<Integer, List<Integer>> adj = new HashMap<>();

            //遍历前置课程信息表，记录入度表和邻接表
            for (int i = 0; i < prerequisites.length; i++) {
                int pre = prerequisites[i][1]; //当前前置课程号
                int post = prerequisites[i][0]; //当前后置课程号 后置会在前置上完后才上
                if (adj.containsKey(pre)) {
                    List<Integer> list = adj.get(pre);
                    list.add(post); //保存其一个出度节点
                    adj.put(pre, list);
                } else {
                    List<Integer> list = new ArrayList<>(){{add(post);}};
                    adj.put(pre, list);
                }
                inDgree[post]++; //当前后置节点有前置节点，他的入度加一。
            }
            System.out.println(Arrays.toString(inDgree));
            System.out.println(adj);
            Queue<Integer> queue = new LinkedList<>();

            //queue的初始化，选择一次遍历将所有入度为0的节点存入
            for (int i = 0; i < numCourses; i++) {
                if (inDgree[i] == 0) queue.offer(i);
            }

            int count = 0; //最终结果判定
            //BFS经典条件
            while (!queue.isEmpty()) {
                int p = queue.poll(); //遍历一个节点
                count++;

                //遍历其所有后置节点，将其入度减一，若因此降为0.将其加入到队列中
                List<Integer> posts = adj.get(p);
                if (posts == null) continue; //存在那种只有没有入度也没有出度的节点【比如说排序中最后一个节点就是】
                for (int post: posts) {
                    inDgree[post]--;
                    if (inDgree[post] == 0) {
                        queue.offer(post);
                    }
                }
            }
            return count == numCourses; //根据有无遍历最大课程数作为返回
         }
    }

    //深度遍历方法实现拓扑排序
    static class Solution {
        /* 
            仍然需要邻接表记录节点的出度节点，用于递归代码中遍历访问，若访问完还没有环，证明这次dfs测试成功，将研途所有flag设置为-1。

            深度遍历方法需要借助一个标志位实现：flag[num]
            flag[i] == 0; 未被访问；
            flag[i] == 1; 被当前这轮深度遍历访问过，因此有环（多次访问）,直接返回false
            flag[i] == -1; 被其他轮遍历访问过，因为其他轮遍历如果有环，肯定不会设置成功-1， 所以他肯定成功了，没有环，我可以返回true
        */
        Map<Integer, List<Integer>> adj;
        int[] flag;
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            adj = new HashMap<>();
            flag = new int[numCourses];
            for (int i = 0; i < prerequisites.length; i++) {
               int pre = prerequisites[i][0];
               int post = prerequisites[i][1];

               if (adj.containsKey(pre)) {
                   List<Integer> list = adj.get(pre);
                   list.add(post);
                   adj.put(pre, list);
               } else {
                   adj.put(pre, new ArrayList<>(){{add(post);}});
               }
           }
           boolean res = true;
           //若已经被探索，没有测试的必要。
            for (int i = 0; i < numCourses && flag[i] == 0; i++) {
                res = res && dfs(i);//当中只有有环，立马返回不能成功分配
                if (!res) {
                    return false;
                }
            }
            return res;
        }

        public boolean dfs (int i) {
            if (flag[i] == 1) return false; //存在环
            if (flag[i] == -1) return true; //已经被验证，不存在环
            //还未被探索，标记被当前轮dfs探索过
            flag[i] = 1;
            List<Integer> posts = adj.get(i);//得到当前节点的后继
            if (posts == null) {
                flag[i] = -1;
                return true; //此时已经为这条路径的终点，已经无需遍历
            }
            boolean res = true;
            for (int post: posts){
                res = res && dfs(post);
                if (!res) return false; //只要有一个后继有环，就宣布失败
            }
            flag[i] = -1;
            return res;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] classes = new int[2][];
        classes[0] = new int[]{1, 0};
        classes[1] = new int[]{0, 1};
        boolean res = s.canFinish(2, classes);
        System.out.println(res);
    }
}
